package com.leetcode.p0;


import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Test77 {

    private List<List<Integer>> res   = new ArrayList<>();
    private Deque<Integer>      stack = new LinkedList<>();

    public List<List<Integer>> combine(int n, int k) {
        if (n <= 0 || k <= 0) {
            return res;
        }

        dfs(0, n, k, 0);

        return res;
    }

    private void dfs(int begin, int n, int k, int lastData) {
        if (begin == k) {
            res.add(new ArrayList<>(stack));
            return;
        }

        for (int i = lastData; i < n; i++) {
            stack.addLast(i + 1);

            dfs(begin + 1, n, k, i + 1);
            stack.removeLast();
        }
    }

    public static void main(String[] args) {
        Test77 test = new Test77();
        System.out.println(test.combine(4, 2));
    }

}
